// 红黑树

function Node(data, left, right, color) {
  this.data = data
  this.left = left || null
  this.right = right || null
  this.color = color || 'black'
}

class RBT {
  constructor() {
    this.root = null
  }

  insert(data) {
    const node = new Node(data)
    
    if(!this.root) {
      this.root = node
    } else {
      let current = this.root

      while(true) {
        if(current.data > data) {
          if(current.left === null) {
            current.left = node
            break
          } 
          current = current.left
        } else {
          if(current.right === null) {
            current.right = node
            break
          }
          current = current.right
        }
      }
    }

    if(!this.isRBT()) {
      this.fixUp()
    }
  }

  remove(data, node = this.root) {
    if(node === null) return null     
    
    if(data === node.data) {
      if(node.left === null && node.right === null) {
        return null
      }

      if(node.left === null) {
        return node.right
      }

      if(node.right === null) {
        return node.left
      }

      const tmpNode = node
      
      node.data = tmpNode.data
      node.right= this.remove(tmpNode.data, node.right)
      
      return node
    } else if(data < node.data) {
      node.left = this.remove(data, node.left)
      return node
    } else {
      node.right = this.remove(data, node.right)
      return node
    }

		if(!isRBT()) {
			fixUp()
		}
  }

  find(data) {
    let current = this.root
    while(true) {
      if(data === current.data) {
        return current
      }
      current = data < current.data ? current.left : current.right

      if(current === null) {
        return null
      }
    }
  }

  rotateR(node) {
    const n = node.left
    
    node.left = n.right
    n.right = node

    n.color = node.color
    node.color = 'RED'

    return n
  }

  rotateL(node) {
    const n = node.ritht
    
    node.right = n.left
    n.left = node

    node.color = n.color
    n.color = 'RED'

    return n    
  }

  inOrder(node) {
    if(node) {
      this.inOrder(node.left)
      console.log(node.data)
      this.inOrder(node.right)
    }
  }
  preOrder(node) {
    if(node) {
      console.log(node.data)
      this.preOrder(node.left)
      this.preOrder(node.right)
    }  
  }

  postOrder(node) {
    if(node) {
      this.postOrder(node.left)
      this.postOrder(node.right)
      console.log(node.data)
    }
  }

  setColor(node, color) {
    if(node) {
      node.color = color || 'RED'  
    }
  }

  isRBT() {
    if(this.root === null) {
      return true
    }
    
    if(this.root.color !== 'RED') {
      return false
    }

    let blackcount = 0
    
    return true
  }

  fixUp(node) {
      
  }

} 

const rbt = new RBT()

rbt.insert(1)
rbt.insert(2)
rbt.insert(3)
rbt.insert(4)
rbt.insert(5)
rbt.insert(6)

rbt.remove(6)

rbt.inOrder(rbt.root)
rbt.preOrder(rbt.root)
rbt.postOrder(rbt.root)

rbt.inOrder()

console.log(rbt.find(1))
